"""
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
"""


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head.next or not head: return head
        h = ListNode(-1)
        h.next = head
        pre = h
        cur = head
        i = 1
        while i < m:
            pre = cur
            cur = cur.next
            i += 1

        t1 = pre
        t2 = cur

        while i <= n:
            lat = cur.next
            cur.next = pre
            pre = cur
            cur = lat
            i += 1

        t1.next = pre
        t2.next = cur
        return h.next


s = Solution()
a1 = ListNode(1)
a2 = ListNode(2)
a3 = ListNode(3)
a4 = ListNode(4)
a5 = ListNode(5)
a4.next = a5
a3.next = a4
a2.next = a3
a1.next = a2
print(s.reverseBetween(a1,2,4))